home *** CD-ROM | disk | FTP | other *** search
/ Programmer Power Tools / Programmer Power Tools.iso / asmutl / conv_a11.arc / POSBM2.ASM < prev    next >
Assembly Source File  |  1989-11-06  |  6KB  |  209 lines
  1. ;Faster string search routine to substitute the POS()
  2. ;function in Turbo Pascal 4 or 5.
  3. ;Based on the Boyer-Moore algorithm.
  4. ;Program Author: Costas Menico (Dr Dobbs, Jul 89)
  5. ;
  6. ;Declare as follows:
  7. ;    {$F+}
  8. ;    {$L SEARCH.OBJ}
  9. ;    FUNCTION posBM(pat,str : STRING) : BYTE; EXTERNAL;
  10. ;Call as follows:
  11. ;    location := posBM(pat, str);
  12. ;
  13. ;Courtesy of Toad Hall
  14. ;v1.2    Toad Hall, 5 Nov 89
  15. ;    Tightening up a little more
  16. ;v1.1    Toad Hall Tweaks, 11 Jun 89
  17. ; -    Very minor, no functional changes
  18.  
  19. SKIPARRLENGTH    EQU    256    ;length of the skip array
  20.  
  21. ;function work stack
  22. dstk    STRUC
  23. patlen    DW    ?        ;pattern length (also BP base work area)
  24. strlen    DW    ?            ;str length
  25. skiparr    DB    SKIPARRLENGTH DUP(?)    ;skip array
  26. ;v1.2    We aren't saving pattern and string text addresses any more,
  27. ;    instead using them directly from the function parameters
  28. ;pattxt    DD    0            ;pattern address
  29. ;strtxt    DD    0            ;string text address
  30. dstk    ENDS
  31.  
  32. ;Total stack (caller's plus work stack)
  33. cstk    STRUC
  34. ourdata    DB    SIZE dstk DUP(?)    ;work stack size
  35. bpsave    DW    0            ;save BP here
  36. retaddr    DD    0            ;points to return address
  37. straddr    DD    0            ;points to string address
  38. pataddr    DD    0            ;points to pattern address
  39. cstk    ENDS
  40.  
  41. PARAMSIZE    EQU SIZE pataddr + SIZE straddr    ;size ofr parameter list
  42.  
  43. PUBLIC    PosBM                ;function name declaration
  44.  
  45. CODE    SEGMENT PARA PUBLIC 'CODE'
  46.     ASSUME    CS:CODE
  47.  
  48. ;Entry point to POSBM function
  49.  
  50. PosBM    PROC    FAR
  51.     push    bp
  52.     sub    sp,SIZE dstk        ;create work area
  53.     mov    bp,sp
  54.  
  55.     push    DS            ;save caller's DS
  56.     xor    ah,ah            ;clear  MSB
  57.     cld
  58.  
  59. ;Get and save pattern length and address
  60.     lds    si,[bp.pataddr]
  61. ;v1.2    mov    WORD PTR [bp.pattxt][2],DS
  62.     lodsb                ;get pattern length (1 byte)
  63.     or    al,al            ;if length is null
  64.     jnz    NotNullP
  65.      jmp    NoMatch            ; then exit
  66.  
  67. NotNullP:
  68.     mov    cx,ax            ;save pattern len to check if 1 later
  69.  
  70.     mov    [bp.patlen],ax        ;save pattern length
  71. ;v1.2    mov    WORD PTR [bp.pattxt],si    ;save address
  72.     inc    word ptr [bp.pataddr]    ;bump pattern address        v1.2
  73.  
  74. ;Get and save string text length and address
  75.     lds    si,[bp.straddr]
  76. ;v1.2    mov    WORD PTR [bp.strtxt][2],DS
  77.     lodsb                ;get string length
  78.     or    al,al            ;if string text is null
  79.     jnz    NotNullS
  80.     jmp    NoMatch            ; then exit
  81.  
  82. NotNullS:
  83.     mov    [bp.strlen],ax        ;save string length
  84. ;v1.2    mov    WORD PTR [bp.strtxt],si    ;save address
  85.     inc    word ptr [bp.straddr]    ;bump string address by 1    v1.2
  86.  
  87. ;v1.2    cmp    cx,1            ;is pattern length 1 char?
  88.     cmp    cl,1            ;is pattern length 1 char?    v1.2
  89.                     ;(CH guaranteed 0)        v1.2
  90.     jne    Do_Boyer_Moore        ;nope
  91.  
  92. ;v1.2    lds    si,[bp.pattxt]        ;yes, do a straight search
  93.     lds    si,[bp.pataddr]        ;yes, do a straight search    v1.2
  94.     mov    cx,ax            ;still has string length    v1.1
  95.     lodsb                ;get the single char pattern
  96. ;v1.2    les    di,[bp.strtxt]        ;get string address
  97.     les    di,[bp.straddr]        ;get string address        v1.2
  98.     repne    scasb            ;search
  99.     jz    Match1            ;found - adjust last DI psn
  100.      jmp    NoMatch            ;not found, exit
  101.  
  102. Match1:
  103.     mov    si,di
  104.     dec    si            ;adjust SI psn            v1.2
  105.     dec    si            ; by 2                v1.2
  106.     jmp    ExactMatch
  107.  
  108. Do_Boyer_Moore:
  109.  
  110. ;Fill the ASCII character skiparray with the pattern length
  111.     lea    di,[bp.skiparr]        ;get skip array address
  112.     mov    dx,SS
  113.     mov    ES,dx
  114.     mov    al,BYTE PTR [bp.patlen]    ;get pattern size
  115.     mov    ah,al            ;put in AH also
  116.     mov    cx,SKIPARRLENGTH / 2    ;array size
  117.     rep    stosw            ;fill with pattern length
  118.  
  119. ;Replace in the ASCII skiparray the corresponding
  120. ;character offset from the end of the pattern minus 1
  121.  
  122. ;v1.2    lds    si,[bp.pattxt]        ;get pattern address
  123.     lds    si,[bp.pataddr]        ;get pattern address        v1.2
  124.     xor    ah,ah            ;clear MSB            v1.1
  125.     mov    cx,ax            ;AX is still pattern length    v1.1
  126.     dec    cx            ; minus 1
  127.     mov    bx,bp            ;save BP
  128.     lea    bp,[bp.skiparr]        ;get skip array address
  129.  
  130. Fill_SkipArray:
  131.     lodsb                ;get char from pattern
  132.     mov    di,ax            ;use it as an index
  133.     mov    [bp+di],cl        ;store the last skip value
  134.     loop    Fill_SkipArray
  135.  
  136.     lodsb
  137.     mov    di,ax
  138.     mov    [bp+di],cl        ;store the last skip value
  139.     mov    bp,bx            ;restore BP
  140.  
  141. ;Now initialize our pattern and string text pointers
  142. ;to start searching
  143. ;v1.2    lds    si,[bp.strtxt]        ;string address
  144.     lds    si,[bp.straddr]        ;string address            v1.2
  145.     lea    di,[bp.skiparr]        ;skip array address
  146.     mov    dx,[bp.strlen]        ;string length
  147.     dec    dx            ; minus 1 for each check
  148.     mov    ax,[bp.patlen]        ;pattern length
  149.     dec    ax            ; starting skip value
  150.     xor    bh,bh            ;clear MSB
  151.     std                ;reverse compare
  152.  
  153. ;Get char from text.  Use the char as an index
  154. ;into the skip array, looking for a skip value of 0.
  155. ;If found, execute a brute force search on the pattern.
  156. SearchLast:
  157.     sub    dx,ax            ;check if string exhausted
  158.     jc    NoMatch            ;yes, no match
  159.  
  160.     add    si,ax            ;no - slide pattern with skip value
  161.     mov    bl,[si]            ;get char, use as an index
  162.     mov    al,SS:[di+bx]        ; and get the new skip value
  163.     or    al,al            ;if 0, then possible match
  164.     jne    SearchLast        ; try again by sliding to right
  165.  
  166. ;We have a possible match,
  167. ;therefore do the reverse Brute-force compare
  168.  
  169.     mov    bx,si            ;save string addr
  170.     mov    cx,[bp.patlen]        ;pattern length
  171. ;v1.2    les    di,[bp.pattxt]        ;pattern address
  172.     les    di,[bp.pataddr]        ;pattern address        v1.2
  173.     dec    di            ;adjust
  174.     add    di,cx            ; and add to point to EOS
  175.     repe    cmpsb            ;do reverse compare
  176.     je    ExactMatch        ;if equal, we found a match
  177.  
  178.     mov    ax,1            ;else set skip value to 1
  179.     lea    di,[bp.skiparr]        ;skip array address
  180.     mov    si,bx            ;get string address
  181.     xor    bh,bh            ;No - clear MSB
  182.     jmp    SHORT SearchLast    ;try again
  183.  
  184. ExactMatch:
  185.     mov    ax,si            ;save current psn in string
  186. ;v1.2    lds    si,[bp.strtxt]        ;get start of strtxt
  187.     lds    si,[bp.straddr]        ;get start of string text    v1.2
  188.     sub    ax,si            ;sub and add 2 to get psn
  189.     inc    ax            ; in string text        v1.2
  190.     inc    ax            ; where pattern is found    v1.2
  191.     jmp    SHORT EndSearch        ;exit function
  192.  
  193. NoMatch:
  194.     xor    ax,ax            ;no match, return a 0
  195.  
  196. EndSearch:
  197.     cld
  198.     pop    DS            ;recover
  199.  
  200.     mov    sp,bp            ;recover last stack psn
  201.     add    sp,SIZE dstk        ;clear up work area
  202.     pop    bp            ;recover BP
  203.     ret    PARAMSIZE        ;return with AX the POSBM value
  204.  
  205. PosBM    ENDP
  206.  
  207. CODE    ENDS
  208.     END
  209.